package com.example.tencentTrain;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 *
 *  示例 1：
 * 输入：matrix =
 *  [[1,2,3],
 *   [4,5,6],
 *   [7,8,9]]
 * 输出：[1,2,3,6,9,8,7,4,5]
 *
 */
public class Leetcode54_SpiralOrder {
    public static void main(String[] args) {
        int[][] matrix = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8 ,9}};
        List<Integer> res = new Solution().spiralOrder(matrix);
        System.out.println(res);
    }

    static class Solution {
        /**
         * 一圈一圈遍历
         * 每圈按照从左到右(上边),从上到下(右边),从右到左(下边),从下到上(左边)
         * @param matrix
         * @return
         */
        public List<Integer> spiralOrder1(int[][] matrix) {
            List<Integer> res = new ArrayList<>();
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return res;

            int rows = matrix.length, columns = matrix[0].length;
            int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
            while (left <= right && top <= bottom) { // 循环一次,内部完成一层的遍历

                // 从左到右
                for (int column = left; column <= right; column++) {
                    res.add(matrix[top][column]);
                }
                // 从上到下
                for (int row = top + 1; row <= bottom; row++) {
                    res.add(matrix[row][right]);
                }

                if (left < right && top < bottom) {
                    // 从右到左
                    for (int column = right - 1; column > left; column--) {
                        res.add(matrix[bottom][column]);
                    }
                    // 从下到上
                    for (int row = bottom; row > top; row--) {
                        res.add(matrix[row][left]);
                    }
                }

                left++;
                right--;
                top++;
                bottom--;
            }

            return res;
        }


        public List<Integer> spiralOrder(int[][] matrix) {
            return spiralOrder1(matrix);
        }
    }
}
